This invention relates to error correcting codes, and more particularly to methods and apparatus for implementing such codes. Basically, the function of an error correcting code is to allow information bits to be recovered after they have been transmitted through a medium which randomly causes errors in some of the bits.
To do this, the information bits that are to be transmitted are used to generate parity bits. Then the information bits and parity bits are both transmitted through the error causing medium. Due to this transmission, some of the transmitted information bits and the transmitted parity bits are received with random errors. However, based on the error correcting code, the originally transmitted information bits may be recovered from the erroneously received information bits and parity bits.
These codes have a variety of applications. For example, when digital information is transmitted through the air, it quite often is encoded in with an error correcting code. This is because the transmission media has noise, and this causes errors during transmission. Thus, when the information is received, the error correcting code allows the original information to be recovered, even though some of the bits were received in error.
In the prior art, a variety of error correcting codes exist. See, for example, Golay, M. J. E., "Binary Coding", IRE Transactions on Information Theory, IT-4, PP. 23-28, September, 1954. Also see, for example, Townsend R. L. and Weldon, Jr., E. J., "Self-Orthogonal Quasi-Cycle Codes" IEEE Transactions on Information Theory, IT-13, April, 1967.
These and other codes, however, are substantially different than the disclosed code. For example, the Golay code requires complex decoding methods and apparatus; while in comparison, the disclosed code uses very simple decoding methods and apparatus. Also, by comparison, the Townsend code has a different error correcting capability. It guarantees to correct 3 errors out of 36 consecutive bits; whereas the disclosed code guarantees to correct 3 errors out of 26 consecutive bits.
Therefore, it is one object of the invention to provide an improved method of encoding information in an error correcting code.
Another object of the invention is to provide an improved method of decoding transmitting information in an error correcting code.
Another object of the invention is to provide improved apparatus for encoding information in an error correcting code.
Still another object of the invention is to provide improved apparatus for decoding transmitted information from received encoded information having random errors.